package J5_29;

import java.util.PriorityQueue;
import java.util.Scanner;

public class test {
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int[] count = new int[26];
        while (in.hasNext()) { // 注意 while 处理多个 case
            char[] ch = in.next().toCharArray();
            for (int i = 0; i < ch.length; i++) {
                count[ch[i] - 'a']++;
            }
        }
        int max = 0, pos = 0;
        for (int i = 0; i < 26; i++) {
            if (count[i] > max) {
                max = count[i];
                pos = i;
            }
        }
        System.out.println((char) ('a' + pos));
    }

    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) { // 注意 while 处理多个 case
            String str = in.next();
            int[] count = new int[256];
            for (int i = 0; i < str.length(); i++) {
                count[str.charAt(i)]++;
            }
            PriorityQueue<Integer> queue = new PriorityQueue<>();
            for (int a : count) {
                if (a > 0) {
                    queue.offer(a);
                }
            }
            int res = 0;
            while (queue.size() > 1) {
                int a = queue.poll();
                int b = queue.poll();
                res += a + b;
                queue.offer(a + b);
            }
            System.out.println(res);
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int len = (int)Math.sqrt(n);
        int[][] dp = new int[len+1][n+1];
        for (int i = 1; i <= n; i++) {
            dp[0][i] = 0x3f3f3f3f;
        }
        for (int i = 1; i <= len; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= i * i) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - i * i] + 1);
                }
            }
        }
        System.out.println(dp[len][n]);
    }

    //集团里有 n 名员工，他们可以完成各种各样的工作创造利润。
    //
    //第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。
    //
    //工作的任何至少产生 minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。
    //
    //有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int len = group.length;
        final int MOD = 1000000007;
        int[][][] dp = new int[len + 1][n + 1][minProfit + 1];
        for (int i = 0; i <= n; i++) {
            dp[0][i][0] = 1;
        }
        for (int i = 1; i <= len; i++) {
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= minProfit; k++) {
                    dp[i][j][k] = dp[i-1][j][k];
                    if (group[i-1] <= j) {
                        dp[i][j][k] += dp[i-1][j-group[i-1]][Math.max(0,k-profit[i-1])];
                        dp[i][j][k] %= MOD;
                    }
                }
            }
        }
        return dp[len][n][minProfit];

    }
}
